package leetcode.code2232;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public String minimizeResult(String expression) {
		char[] cs = expression.toCharArray();
		int p = 0;
		char c = 1;
		int num1 = 0, base1 = 1, size1 = 0;
		while ((c = cs[p]) != '+') {
			num1 = num1 * 10 + c - '0';
			base1 *= 10;
			size1++;
			p++;
		}
		p++;
		int len = cs.length;
		int num2 = 0, base2 = 1, size2 = 0;
		while (p < len) {
			num2 = num2 * 10 + cs[p] - '0';
			base2 *= 10;
			size2++;
			p++;
		}
		base2 /= 10;
		int[][] nums1 = new int[size1][2];
		nums1[0][0] = 1;
		for (int i = 0; i < nums1.length; i++) {
			nums1[i][0] += num1 / base1;
			nums1[i][1] = num1 % base1;
			base1 /= 10;
		}
		int[][] nums2 = new int[size2][2];
		for (int i = 0; i < nums2.length; i++) {
			nums2[i][0] = num2 / base2;
			nums2[i][1] = num2 % base2;
			base2 /= 10;
		}
		nums2[size2 - 1][1] = 1;
		int min = Integer.MAX_VALUE;
		StringBuffer ans = null;
		for (int i = 0; i < size1; i++) {
			for (int j = 0; j < size2; j++) {
				int cur = nums1[i][0] * (nums1[i][1] + nums2[j][0]) * nums2[j][1];
				if (cur < min) {
					ans = new StringBuffer();
					min = cur;
					if (i != 0) {
						ans.append(nums1[i][0]);
					}
					ans.append('(').append(nums1[i][1]).append('+').append(nums2[j][0]).append(')');
					if (j != size2 - 1) {
						ans.append(nums2[j][1]);
					}
				}
			}
		}
		return ans.toString();
	}

	@Override
	public void debug4() {
		H.compare("2(47+38)", this.minimizeResult("247+38"));
		H.compare("1(2+3)4", this.minimizeResult("12+34"));
		H.compare("(999+999)", this.minimizeResult("999+999"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
